//测试-二叉树
//编译：g++ TestBinaryTree.cpp ../../*/*/BinaryTree.hpp -o test
#ifndef __TESTBINARYTREE__CPP
#define __TESTBINARYTREE__CPP

#include<iostream>
#include"../../DataStructure/Tree/BinaryTree.hpp"

using namespace std;
using namespace NgSiuKei;

int main(void) {
    binary_tree_node<char> *treeA = createTree('a', (binary_tree_node<char> *)nullptr, (binary_tree_node<char> *)nullptr);
    binary_tree_node<char> *treeB = createTree('b', (binary_tree_node<char> *)nullptr, (binary_tree_node<char> *)nullptr);
    binary_tree_node<char> *treeC = createTree('c', (binary_tree_node<char> *)nullptr, (binary_tree_node<char> *)nullptr);
    binary_tree_node<char> *treeD = createTree('d', (binary_tree_node<char> *)nullptr, (binary_tree_node<char> *)nullptr);
    binary_tree_node<char> *treeE = createTree('e', (binary_tree_node<char> *)nullptr, (binary_tree_node<char> *)nullptr);
    binary_tree_node<char> *treeF = createTree('f', (binary_tree_node<char> *)nullptr, (binary_tree_node<char> *)nullptr);

    // 前序：a b d e c f
    // 中序：d b e a f c
    // 后序：d e b f c a
    // 层序：a b c d e f
    // insertLeftSubTree(treeA, treeB);
    // insertRightSubTree(treeA, treeC);
    // insertLeftSubTree(treeB, treeD);
    // insertRightSubTree(treeB, treeE);
    // insertLeftSubTree(treeC, treeF);

    // 前序：a b d e c f
    // 中序：d b e a c f
    // 后序：d e b f c a
    // 层序：a b c d e f
    // insertLeftSubTree(treeA, treeB);
    // insertRightSubTree(treeA, treeC);
    // insertLeftSubTree(treeB, treeD);
    // insertRightSubTree(treeB, treeE);
    // insertRightSubTree(treeC, treeF);

    // 前序：a b d c e f
    // 中序：d b a e c f
    // 后序：d b e f c a
    // 层序：a b c d e f
    // insertLeftSubTree(treeA, treeB);
    // insertRightSubTree(treeA, treeC);
    // insertLeftSubTree(treeB, treeD);
    // insertLeftSubTree(treeC, treeE);
    // insertRightSubTree(treeC, treeF);

    // 前序：a b d c e f
    // 中序：b d a e c f
    // 后序：d b e f c a
    // 层序：a b c d e f
    // insertLeftSubTree(treeA, treeB);
    // insertRightSubTree(treeA, treeC);
    // insertRightSubTree(treeB, treeD);
    // insertLeftSubTree(treeC, treeE);
    // insertRightSubTree(treeC, treeF);

    // 前序：a b d f e c
    // 中序：f d b e a c
    // 后序：f d e b c a
    // 层序：a b c d e f
    // insertLeftSubTree(treeA, treeB);
    // insertRightSubTree(treeA, treeC);
    // insertLeftSubTree(treeB, treeD);
    // insertRightSubTree(treeB, treeE);
    // insertLeftSubTree(treeD, treeF);

    // 前序：a b d f e c
    // 中序：d f b e a c
    // 后序：f d e b c a
    // 层序：a b c d e f
    // insertLeftSubTree(treeA, treeB);
    // insertRightSubTree(treeA, treeC);
    // insertLeftSubTree(treeB, treeD);
    // insertRightSubTree(treeB, treeE);
    // insertRightSubTree(treeD, treeF);

    // 前序：a b c d e f
    // 中序：a c b d f e
    // 后序：c f e d b a
    // 层序：a b c d e f
    insertRightSubTree(treeA, treeB);
    insertLeftSubTree(treeB, treeC);
    insertRightSubTree(treeB, treeD);
    insertRightSubTree(treeD, treeE);
    insertLeftSubTree(treeE, treeF);

    U_L_L num = getTreeNodeNum(treeA);
    U_L_L height = getTreeHeight(treeA);
    cout << "num = " << num << endl;
    cout << "height = " << height << endl;

    char *preArray = orderTree(treeA, ORDER_TYPE_PRE);
    char *inArray = orderTree(treeA, ORDER_TYPE_IN);
    char *postArray = orderTree(treeA, ORDER_TYPE_POST);
    char *levelArray = orderTree(treeA, ORDER_TYPE_LEVEL);

    cout << "前序 = [ ";
    for(U_L_L i=0; i<num; ++i) {
        cout << preArray[i] << ' ';
    }
    cout << ']' << endl;

    cout << "中序 = [ ";
    for(U_L_L i=0; i<num; ++i) {
        cout << inArray[i] << ' ';
    }
    cout << ']' << endl;

    cout << "后序 = [ ";
    for(U_L_L i=0; i<num; ++i) {
        cout << postArray[i] << ' ';
    }
    cout << ']' << endl;

    cout << "层序 = [ ";
    for(U_L_L i=0; i<num; ++i) {
        cout << levelArray[i] << ' ';
    }
    cout << ']' << endl;

    //复制
    cout << "————复制————" << endl;
    binary_tree_node<char> *copyT = copyTree(treeA);
    cout << "treeA = " << treeA << endl;
    cout << "copyT = " <<copyT << endl;

    num = getTreeNodeNum(copyT);
    height = getTreeHeight(copyT);
    cout << "num = " << num << endl;
    cout << "height = " << height << endl;

    char *preCopyArray = orderTree(copyT, ORDER_TYPE_PRE);
    char *inCopyArray = orderTree(copyT, ORDER_TYPE_IN);
    char *postCopyArray = orderTree(copyT, ORDER_TYPE_POST);
    char *levelCopyArray = orderTree(copyT, ORDER_TYPE_LEVEL);

    cout << "前序 = [ ";
    for(U_L_L i=0; i<num; ++i) {
        cout << preCopyArray[i] << ' ';
    }
    cout << ']' << endl;

    cout << "中序 = [ ";
    for(U_L_L i=0; i<num; ++i) {
        cout << inCopyArray[i] << ' ';
    }
    cout << ']' << endl;

    cout << "后序 = [ ";
    for(U_L_L i=0; i<num; ++i) {
        cout << postCopyArray[i] << ' ';
    }
    cout << ']' << endl;

    cout << "层序 = [ ";
    for(U_L_L i=0; i<num; ++i) {
        cout << levelCopyArray[i] << ' ';
    }
    cout << ']' << endl;

    clearTree(treeA);
    clearTree(copyT);
    delete preArray;
    delete inArray;
    delete postArray;
    delete levelArray;
    delete preCopyArray;
    delete inCopyArray;
    delete postCopyArray;
    delete levelCopyArray;
    if(nullptr == treeA) {
        cout << "CNM" << endl;
    }

    return 0;
}

#endif